package advanced.class04;

import java.util.*;

/**
 * 创建大楼的轮廓线：
 * 		给定一个N行3列的数组，每一行杠表示一座大楼，一共有N座大楼
 * 		所有大楼的底部都坐落在X轴上，每一行的三个值（a,b.c）分别表示大楼的开始位置，大楼的结束位置，大楼的高度
 * 		现在给你一排大楼的数组
 * 		要求你绘制出大楼的轮廓线
 *
 */
public class Code_01_Building_Outline {

	// 定义位置信息类
	public static class Node {
		boolean isUp;         // 该点是上还是下
		int posi;             // 该点的坐标位置
		public int h;         // 该点的高度

		public Node(boolean bORe, int position, int height) {
			isUp = bORe;
			posi = position;
			h = height;
		}
	}

	// 定义一个比较器： 按照Node节点的posi位置来排序，如果两个点的位置相同，则向下的位置在前面
	public static class NodeComparator implements Comparator<Node> {
		@Override
		public int compare(Node o1, Node o2) {
			if (o1.posi != o2.posi) {
				return o1.posi - o2.posi;
			}
			if (o1.isUp != o2.isUp) {
				return o1.isUp ? -1 : 1;
			}
			return 0;
		}
	}

	// 建立轮廓线的主函数
	public static List<List<Integer>> buildingOutline(int[][] buildings) {
		// 改造提供的原始轮廓线，并排序
		Node[] nodes = new Node[buildings.length * 2];
		for (int i = 0; i < buildings.length; i++) {
			nodes[i * 2] = new Node(true, buildings[i][0], buildings[i][2]);
			nodes[i * 2 + 1] = new Node(false, buildings[i][1], buildings[i][2]);
		}
		Arrays.sort(nodes, new NodeComparator());

		//--------------------遍历Node数组，获取每个位置的最大高度-----------------------
		TreeMap<Integer, Integer> htMap = new TreeMap<>();    // 代表某一个高度h出现的次数
		TreeMap<Integer, Integer> pmMap = new TreeMap<>();    // 代表每个节点位置的当前最大高度
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i].isUp) {
				if (!htMap.containsKey(nodes[i].h)) {
					htMap.put(nodes[i].h, 1);
				} else {
					htMap.put(nodes[i].h, htMap.get(nodes[i].h) + 1);
				}
			} else {
				if (htMap.containsKey(nodes[i].h)) {
					if (htMap.get(nodes[i].h) == 1) {   // 如果当前高度只有一个了，那么直接将此高度删除即可
						htMap.remove(nodes[i].h);
					} else {
						htMap.put(nodes[i].h, htMap.get(nodes[i].h) - 1);
					}
				}
			}
			//-------更新当前位置的最大高度--------
			if (htMap.isEmpty()) {
				// 如果当前的htMap清空了，那么当前位置的最大高度置为0
				pmMap.put(nodes[i].posi, 0);
			} else {
				// 如果htMap不为null，那么当前位置的最大高度就是htMap中的最大的键值
				pmMap.put(nodes[i].posi, htMap.lastKey());
			}
		}
		//----------- 生成结果集对象，只需要用到pmMap -----------------
		List<List<Integer>> res = new ArrayList<>();
		int start = 0;
		int height = 0;
		for (Integer curPosition : pmMap.keySet()) {
			int curMaxHeight = pmMap.get(curPosition);
			if(height != curMaxHeight){
				if(height != 0){
					List<Integer> newRecord = new ArrayList<>();
					newRecord.add(start);
					newRecord.add(curPosition);
					newRecord.add(height);
					res.add(newRecord);
				}
				start = curPosition;
				height = curMaxHeight;
			}
		}
		return res;
	}

}
